Perpustakaan telah ditubuhkan pada 1 Julai 1862 sebagai perpustakaan awam percuma pertama Moscow dengan dinamakan sebagai Perpustakaan Muzium Awam Moscow dan Muzium Rumiantsev atau Perpustakaan Rumiantsev. Ia digelar "Leninka".[3] Muzium Rumyantsev merupakan kompleks muzium awam pertama di Moscow, dan menempatkan koleksi Seni Nikolai Petrovich Rumyantsev, yang telah diberikan kepada rakyat Rusia dan dipindahkan dari St. Petersburg ke Moscow. Sumbangan ini termasuklah semua buku dan manuskrip termasuk juga koleksi numismatik dan etnografi yang banyak. Ia juga terdapat kira-kira 200 buah lukisan dan lebih daripada 20,000 cetakan yang telah dipilih dari kolesi Hermitage di St. Petersburg, dapat dilihat dalam apa yang disebut Rumah Pashkov (istana, yang ditubuhkan antara 1784 dan 1787, berdekatan Kremlin). Tsar Alexander II dari Rusia telah menyumbangkan lukisan The Appearance of Christ before the People oleh Alexander Andreyevich Ivanov semasa pembukaan muzium ini.

Pada tahun-tahun mendatang kemudian, koleksi muzium berkembang dengan sumbangan bahan dan wang yang menyebabkan muzium kemudiannya menjadi tempat penyimpanan lebih banyak koleksi lukisan Eropah Timur yang penting. Koleksi terus berkembang dan menyebabkan bangunan Rumah Pashkov tidak mampu menampung lebih banyak koleksi dan bangunan kedua dibina bersebelahan muzium selepas abad ke-20 untuk menempatkan lukisan itu khususnya.

Selepas Revolusi Oktober koleksinya semakin berkembang dan menyebabkan kekurangan ruang. Masalah kewangan yang teruk turut timbul, memandangkan banyak wang dibelanjakan untuk Muzium Pushkin, yang baharu sahaja selesai beberapa tahun sebelum itu. Oleh itu, pada tahun 1925, diputuskan untuk membubarkan Muzium Rumyantsev dan koleksinya diserahkan kepada muzium-muzium dan institusi di dalam Rusia. Sebahagian telah diserahkan kepada Muzium Pushkin termasuklah seni dan antik Eropah Timur. Rumah Pashkov (di Jalan Mokhovaya) telah dinamakan semula sebagai "Bangunan Lama Perpustakaan Negeri Rusia". Bangunan arkib lama di Jalan Mokhovaya dan Vozdvizhenka telah dirobohkan dan digantikan dengan bangunan baharu.

Peringkat pertama pembinaan, direka oleh Vladimir Shchuko dan Vladimir Gelfreikh pada tahun 1927–1929, telah diberi kuasa pada tahun 1929 dan bermula pada 1930.[4] Peringkat pertama siap pada tahun 1941. Dalam proses itu, bangunan itu menjadi Neoklasisisme moden ciri-ciri luaran Istana Soviet (direka oleh Shchuko dan Gelfreikh).[5] Bahagian terakhir plan Shchuko merupakan dewan bacaan dengan 250 buah tempat duduk yang dibuka pada tahun 1945; dengan penambahan berterusan sehingga tahun 1960.[6] Pada tahun 1968, perpustakaan telah mencapai had kapasitinya, dan pembinaan depositori baharu dilancarkan di Khimki yang diperuntukkan untuk menyimpan surat khabar, karya saintifik dan buku-buku permintaan rendah dari kawasan penyimpanan utama. Peringkat pertama perpustakaan Khimki telah siap pada tahun 1975.[6]

Pada tahun 1925, kompleks ini dinamakan Perpustakaan Negeri V. I. Lenin USSR sebelum ditukar menjadi Perpustakaan Negeri Rusia pada tahun 1992 atas arahan Presiden Boris Yeltsin.[7]